package org.example.datastructure.ch7;

import java.util.ArrayList;
import java.util.List;

public class pQueue {
    public List<Integer> queue;
    public pQueue() {
        queue = new ArrayList<>();
        queue.add(0);
    }
    public pQueue(int[] nums){
        queue = new ArrayList<>();
        queue.add(0);
        for(int num:nums){
            enQueue(num);
        }
    }
    public void enQueue(int x){
        int hole = queue.size();
        queue.add(x);
        while(hole>1&&x<queue.get(hole/2)){
            queue.set(hole,queue.get(hole/2));
            hole = hole/2;
        }
        queue.set(hole,x);
    }
    public int deQueue(){
        int minItem = queue.get(1);
        queue.set(1,queue.get(queue.size()-1));
        percolateDown(1);
        queue.remove(queue.size()-1);
        return minItem;

    }
    private void percolateDown(int hole){
        int child=1;
        int tmp = queue.get(hole);
        while(hole*2<=queue.size()-1){
            child = 2*hole;
            if(queue.get(child+1)<queue.get(child)){
                child++;
            }
            if(queue.get(child)<tmp){
                queue.set(hole,queue.get(child));
            }else{
                break;
            }
            hole = child;
        }
        queue.set(hole,tmp);
    }
}
